// https://leetcode.cn/problems/generate-parentheses/

// 题干：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

// 示例：输入：n = 3
//       输出：["((()))","(()())","(())()","()(())","()()()"]

// 碎语：老规矩先从决策树开始，什么是有效的括号组合？
//       左括号的数量＝右括号的数量
//       从头开始的任意一个子串，左括号的数量大于等于右括号的数量
//       举个例子，当n=3的时候，一个有六个位置，第一个位置的右括号的情况要被剪枝剪掉

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int left, right, n;
    string path;
    vector<string> res;

    vector<string> generateParenthesis(int _n)
    {
        // 剪枝：1.添加左括号的时候，数量小于n
        //       2.right<=left
        n = _n;
        left = 0, right = 0;
        dfs();
        return res;
    }

    void dfs(void)
    {
        if (right == n){
            res.push_back(path);
            return ;
        }

        if (left < n){
            path.push_back('('), left++;

            dfs();
            path.pop_back(),left--;
        }

        if (right < left){  // 左括号的数量大于等于右括号的数量
            path.push_back(')'), right++;

            dfs();
            path.pop_back(), right--;
        }
    }
};

int main()
{
    Solution sol;
    vector<string> index = sol.generateParenthesis(3);

    for (const auto& str : index){
        cout << str << endl;
    }

    return 0;
}